package leetcode.code0382;

import java.util.ArrayList;
import java.util.List;

import leetcode.helper.HelpDebug;
import leetcode.helper.tree.ListNode;

/**
 * 执行用时：11 ms, 在所有 Java 提交中击败了84.85%的用户
 *
 * 内存消耗：40.4 MB, 在所有 Java 提交中击败了55.24%的用户
 *
 * 通过测试用例：8 / 8
 */
public class Solution3 {

	List<Integer> list;
	int size;
	Integer[] nums;

	public Solution3(ListNode head) {
		list = new ArrayList<>();
		size = 0;
		while (head != null) {
			list.add(head.val);
			head = head.next;
			size++;
		}
		nums = list.toArray(new Integer[list.size()]);
	}

	public int getRandom() {
		return nums[(int) (Math.random() * size)];
	}

	public static void main(String[] args) {
		Solution3 so = new Solution3(ListNode.set(HelpDebug.str2array3("[1,2,3,4,5,6]")));
		for (int i = 0; i < 20; i++) {
			System.out.println(so.getRandom());
		}
	}

}
